package com.dh.datastructure;

public class PriorityQue {
	 //数组实际大小
	 private int maxSize;
	 private int[] priQueArray;
	 //队列中的数据个数
	 private int nItems;
	
	 public PriorityQue(int s){
    	maxSize = s;
        priQueArray = new int[maxSize];
        nItems = 0;
	 }
	 
	 //插入数据insert() 方法，
	 //先检查队列中是否有数据项，如果没有，则直接插入到下标为0的单元里，
	 //否则，从数组顶部开始比较，找到比插入值小的位置进行插入，并把 nItems 加1.
	 public void insert(int value) {
		 int j;
		 //如果队列中的个数为是0
		 if(nItems==0) {
			 priQueArray[nItems++] = value;
		 }else {
			 j=nItems-1;
			 //如果插入的值大于队列中最后一个
			 while(j>=0 && value>priQueArray[j]) {
				 priQueArray[j+1] = priQueArray[j];
	             j--;
			 }
			 priQueArray[j+1] = value;
	         nItems++;
		 }
	 }
	//移除数据,由于是按照大小排序的，所以移除数据我们指针向下移动
    //被移除的地方由于是int类型的，不能设置为null，这里的做法是设置为 -1
    public int remove(){
        int k = nItems -1;
        int value = priQueArray[k];
        priQueArray[k] = -1;//-1表示这个位置的数据被移除了
        nItems--;
        return value;
    }
     
    //查看优先级最高的元素
    public int peekMin(){
        return priQueArray[nItems-1];
    }
     
    //判断是否为空
    public boolean isEmpty(){
        return (nItems == 0);
    }
     
    //判断是否满了
    public boolean isFull(){
        return (nItems == maxSize);
    }

}
